home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_high.lha / LEDA-3.1c-high / man / stack.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  1.5 KB  |  52 lines
  1. {\magonebf 3.3 Stacks (stack) }
  2.  
  3. \decl stack E
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance $S$ of the parameterized data type \name\ is 
  8. a sequence of elements of data type $E$, called the element 
  9. type of $S$. Insertions or deletions of elements take place only at one end of 
  10. the sequence, called the top of $S$. The size of $S$ is the length of the 
  11. sequence, a stack of size zero is called the empty stack.
  12.  
  13.  
  14. \bigskip
  15. {\bf 2. Creation}
  16.  
  17. \create S {}   
  18.  
  19. creates an instance \var\ of type \name. \var\ is initialized with the empty 
  20. stack.
  21.  
  22.  
  23. \bigskip
  24. {\bf 3. Operations}
  25. \+\cleartabs & \hskip 2truecm & \hskip 4truecm &\cr
  26. \+\op E       top   {}        
  27.                               {returns the top element of \var}
  28. \+\nop                        {\precond $S$ is not empty.}
  29. \smallskip
  30. \+\op E       pop   {}        
  31.                               {deletes and returns the top element of \var}
  32. \+\nop                        {\precond $S$ is not empty.}
  33. \smallskip
  34. \+\op void    push  {E\ x}    
  35.                               {adds $x$ as new top element to \var.}
  36. \smallskip
  37. \+\op void    clear {}        
  38.                               {makes \var\ the empty stack.}
  39. \smallskip
  40. \+\op int     size  {}        
  41.                               {returns the size of \var.}
  42. \smallskip
  43. \+\op bool    empty {}        
  44.                               {returns true if \var\ is empty, false otherwise.}
  45.  
  46. \bigskip
  47. {\bf 4. Implementation}
  48.  
  49. Stacks are implemented by singly linked linear lists. All operations take 
  50. time $O(1)$, except clear which takes time $O(n)$, where $n$ is the size of 
  51. the stack.
  52.